package com.czk.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/7/21 20:32
 */
public class Graph {
    // 存储顶点的集合
    private List<String> vertexList;
    // 存储对应的邻接矩阵
    private int[][] edges;
    // 边的数目
    private int numOfEdges;
    // 深度优先遍历，定义数组判断是否被访问过
    private boolean[] isVisited;

    public Graph(int n) {
        vertexList = new ArrayList<>();
        edges = new int[n][n];
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    // 图的深度优先遍历
    // 得到邻接节点的下标
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 获取相领节点下标
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // dfs深度优先搜索
    public void dfs(boolean[] isVisited, int i) {
        // 输出节点
        System.out.print(getValueByIndex(i) + "->");
        // 该节点已经被访问
        isVisited[i] = true;
        // 查找i的第一个邻接节点
        int firstNeighbor = this.getFirstNeighbor(i);
        // 递归
        while (firstNeighbor != -1) {
            if (!isVisited[firstNeighbor]) {
                // 递归
                dfs(isVisited, firstNeighbor);
            }
            // 节点已经被访问后
            // 返回掐一个节点查找
            firstNeighbor = getNextNeighbor(i, firstNeighbor);
        }
    }

    /**
     * 深度优先搜索遍历
     *
     * @param isVisited
     * @param i
     */
    public void dfs_1(boolean[] isVisited, int i) {
        // 拿到当前节点
        System.out.println(getValueByIndex(i));
        // 标记该节点
        isVisited[i] = true;
        // 拿到下一个节点
        int firstNeighbor = getFirstNeighbor(i);
        // 是否被访问
        // 存在
        while (firstNeighbor != -1) {
            // 是否被访问
            if (!isVisited[firstNeighbor]) {
                // 没被访问
                // 再把它当做第一个节点；爱访问
                dfs_1(isVisited, firstNeighbor);
            }
            // 被访问，拿到下一个节点
            firstNeighbor = getNextNeighbor(i, firstNeighbor);
        }
    }

    public void dfs_2(boolean[] isVisited, int i) {
        // 拿到值
        String valueByIndex = getValueByIndex(i);
        System.out.println(valueByIndex + "->");
        // 标记被访问
        isVisited[i] = true;
        // 拿到与其相邻的下一节点
        int firstNeighbor = getFirstNeighbor(i);
        // 遍历
        while (firstNeighbor != -1) {
            // 没被访问
            if (!isVisited[firstNeighbor]) {
                // 继续搜索
                dfs_2(isVisited, firstNeighbor);
            }
            // 被访问拿到下一结点
            firstNeighbor = getNextNeighbor(i, firstNeighbor);
        }
    }

    //
    public void dfs() {
        // 遍历所有节点
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    public void dfs_1() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                // 没被访问
                dfs_1(isVisited, i);
            }
        }
    }

    //广度优先遍历的算法
    public void bfs(boolean[] isVisited, int i) {
        int u;//  访问队列头结点对应的下标
        int w;// 领接节点w
        // 队列，记录访问的节点信息
        LinkedList queue = new LinkedList();
        // 输出节点信息
        System.out.print(getValueByIndex(i) + "->");
        // 标记为已访问
        isVisited[i] = true;
        // 将节点加入队列
        queue.addLast(i);
        //
        while (!queue.isEmpty()) {
            // 取出队列头下标
            u = (Integer) queue.removeFirst();
            // 得到第一个邻接节点下标
            w = getFirstNeighbor(u);
            while (w != -1) {
                // 是否访问过
                if (!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "->");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                // 访问过，以u为前驱点找w后面的第一个节点
                w = getNextNeighbor(u, w);
            }
        }
    }

    /**
     * 图的广度优先搜索
     *
     * @param isVisited
     * @param i
     */
    public void bfs_1(boolean[] isVisited, int i) {
        // 头结点
        int v;
        // 邻接节点
        int w;
        // 将该节点标记为已访问
        isVisited[i] = true;
        // 将该节点加入队列
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.println(getValueByIndex(i));
        queue.addLast(i);
        // 队列不为空
        while (!queue.isEmpty()) {
            v = queue.removeFirst();
            // 拿到第一个邻接节点
            w = getFirstNeighbor(i);
            // 是否被访问
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.print(getValueByIndex(w));
                    // 标记为访问
                    isVisited[w] = true;
                    // 将其放入队列
                    queue.addLast(w);
                }
                // 体现出广度优先
                w = getNextNeighbor(v, w);
            }
        }


    }

    public void bfs_2(boolean[] isVisited, int i) {
        // 拿到
        String valueByIndex = getValueByIndex(i);
        System.out.println(valueByIndex + "->");
        // 创建队列
        isVisited[i] = true;
        // 定义头结点
        int u;
        int w;
        LinkedList<Integer> queue = new LinkedList();
        queue.addLast(i);
        // 遍历
        while (!queue.isEmpty()) {
            // 拿到第一个
            u = queue.removeFirst();
            // 拿到相邻
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    // 拿到值
                    System.out.println(getValueByIndex(w) + "->");
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w);
            }

        }
    }

    // 遍历所有节点都进行广度优先搜索
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    public void bfs_1() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs_1(isVisited, i);
            }
        }
    }

    // 添加节点
    public void add(String vertex) {
        vertexList.add(vertex);
    }
    // 添加边

    /**
     * @param v1     v1表示第一个顶点的下表
     * @param v2     v2表示第二个顶点的下标
     * @param weight 表示权值（怎么样表示连通，怎么样表示不连通）
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        // 由于是无向图
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    // 节点个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 返回对应节点的下标的值
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    // 返回v1和v2的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 显示图对应的矩阵
    public void showGraph() {
        // 遍历数组
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public static void main(String[] args) {
        // 测试数组
        // 节点的个数
        int n = 5;
        String[] vertexValue = {"A", "B", "C", "D", "E"};
        // 创图对象
        Graph graph = new Graph(n);
        for (String s : vertexValue) {
            graph.add(s);
        }
        // 添加边A->B
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        // 显示邻接矩阵
        graph.showGraph();
        graph.dfs_1();
        //graph.bfs_1();
    }
}

